import java.util.*;

class NumArray {
    int[] tree;
    int n;
    public NumArray(int[] nums) {
        n=nums.length;
        tree=new int[n*2];
        for(int i=n,j=0;i<2*n;i++,j++){
            tree[i]=nums[j];
        }
        for(int i=n-1;i>0;i--){
            tree[i]=tree[i*2]+tree[i*2+1];
        }
    }

    public void update(int index, int val) {
        index+=n;
        int value=val-tree[index];
        while (index>0){
            tree[index]+=value;
            index/=2;
        }
    }

    public int sumRange(int left, int right) {
        int sum=0;
        left+=n;
        right+=n;
        while (left<=right){
            if(left%2==1){
                sum+=tree[left];
                left++;
            }
            if(right%2==0){
                sum+=tree[right];
                right--;
            }
            left/=2;
            right/=2;
        }
        return sum;
    }
}























public class project {
    public int translateNum(int num) {
        if(num<=9){
            return 1;
        }
        int tmp=num%100;
        if(tmp<=9||tmp>=26 ){
            return translateNum(num/10);
        }else{
            return (translateNum(num/10)+translateNum(num/100));
        }
    }
















    int[][] dirs={{-1,0},{1,0},{0,-1},{0,1}};
    public int orangesRotting(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int count=0;
        int rotCount=0;
        Queue<int[]> queue=new ArrayDeque<>();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==0){
                    continue;
                }else if(grid[i][j]==2){
                    queue.add(new int[]{i,j});
                    rotCount++;
                }
                count++;
            }
        }
        if(count==0){
            return 0;
        }
        if(rotCount==0){
            return -1;
        }
        int ret=0;
        while (queue.size()>0){
            int size=queue.size();
            for(int i=0;i<size;i++){
                int[] arr=queue.poll();
                for(int[] dir:dirs){
                    int x=arr[0]+dir[0];
                    int y=arr[1]+dir[1];
                    if(!find(grid,x,y,row,col)){
                        continue;
                    }
                    rotCount++;
                    grid[x][y]=2;
                    queue.add(new int[]{x,y});
                }
            }
            ret++;
        }
        if(rotCount<count){
            return -1;
        }
        return ret-1;
    }
    public boolean find(int[][] grid,int x,int y,int row,int col){
        return x>=0&&x<row&&y>=0&&y<col&&grid[x][y]==1;
    }














    public int flipgame(int[] fronts, int[] backs) {
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<fronts.length;i++){
            if(fronts[i]==backs[i]){
                set.add(fronts[i]);
            }
        }
        int min=Integer.MIN_VALUE;
        for(int i=0;i<fronts.length;i++){
            if(!set.contains(fronts[i])){
                min=Math.min(min,fronts[i]);
            }
        }
        for(int i=0;i<backs.length;i++){
            if(!set.contains(backs[i])){
                min=Math.min(min,backs[i]);
            }
        }
        return min%Integer.MAX_VALUE;
    }
















    public boolean hasAllCodes(String s, int k) {
        if(s.length()<(1<<k)+k-1){
            return false;
        }
        Set<String> set=new HashSet<>();
        for(int i=0;i<=s.length()-k;i++){
            set.add(s.substring(i,i+k));
        }
        return set.size()==(1<<k);
    }

}
